home *** CD-ROM | disk | FTP | other *** search
/ Experimental BBS Explossion 3 / Experimental BBS Explossion III.iso / c / rle16_sc.zip / RLE16.DOC < prev    next >
Text File  |  1993-05-10  |  5KB  |  119 lines
  1.  
  2. Run Length Encoding compressor program 16 bit header version
  3.  
  4. Written by Shaun Case 1991 in Borland C++ 2.0
  5.                               with sizeof (int) == 2
  6.  
  7. This program and its source code are Public Domain.
  8. This program should be portable to any machine with
  9. 2 byte short ints and 8 bit bytes.
  10.  
  11.  
  12. What is run length encoding?
  13.  
  14. Run Length Encoding, also known as RLE, is a method of compressing data
  15. that has a lot of "runs" of bytes (or bits) in it.  A "run" is a series
  16. of bytes that are all the same. For instance, the string "THIS IS A
  17. VEEEEEEEEEEEEEEEEEEEEEEEERY INTERESTING SENTENCE" has a run of 23 'E's
  18. in it.  This could be compressed in the following manner:
  19.  
  20. THIS IS A V23ERY INTERESTING SENTENCE
  21.  
  22. resulting in a savings of 20 characters.  A further savings of one
  23. character can be realized if the sequence "23" is replaced by a single
  24. byte with the value 23.
  25.  
  26. However, if the text to be encoded is arbitrary, then it may contain
  27. numbers as well as letters, and bytes of all possible values.  For this
  28. reason, there must be some way to let the decoder know when a compressed
  29. run is encountered, and when a sequence to be passed straight through is
  30. encountered.  For this reason, the following file format was used:
  31.  
  32.  
  33. ========= tech info =========
  34.  
  35. 16 bit header version.
  36.  
  37. File format:
  38.  
  39. 13 bytes : original filename, followed by:
  40.  
  41. [ 16 bit header + data ][ 16 bit header + data ][16 bit header + data ]
  42. etc..
  43.  
  44. header:
  45. [lo byte][hi byte] ==> turn into 16 bit int ==>
  46.  
  47.   bit 15        : 1 if following byte is a run
  48.   bit 14 - 0    : length of run (max 32767, min 4)
  49.  
  50. data: 1 byte : which character run consists of
  51.  
  52. *** OR ***
  53.  
  54. header:
  55. [lo byte][hi byte] ==> turn into 16 bit int ==>
  56.  
  57.   bit 15        : 0 if following bytes are sequence
  58.   bit 14 - 0    : length of sequence (max 32767)
  59.  
  60. data:  (header & 0x7FFF) bytes of data
  61.                 : data bytes copied to output stream unchanged
  62.  
  63. ===============================
  64.  
  65. bugs:
  66.  
  67.         None known
  68.  
  69.  
  70. Nasty features :
  71.  
  72.         1)  In 8 bit version, when encoder reaches max run length, it is
  73.             written out correctly, but is followed by a 1 length run of
  74.             the next byte.  Odd.  Reason unknown.  This version
  75.             probably does it too, but I haven't tested it.
  76.  
  77.         2)  Better compression could be achieved by having min
  78.             compression length and sequence length understood to be 4.
  79.             This would allow an "understood" multiplication of the
  80.             seq_len or run_len by 4, since 1 is never (should never be)
  81.             used, allowing sequences of 131068 bytes.
  82.  
  83.             Implementing this requires fixing 1 above, too.
  84.  
  85.         4)  This 16 bit "improvement" is very unlikley to give better
  86.             compresssion than the 8 bit version for data consisting of
  87.             executable code, English or or other natural language text,
  88.             netnews, BBS messages, or just about anything else other
  89.             than large simple graphics images or other types of data
  90.             that consist almost entirely of very long runs of
  91.             characters.  In most cases, this program will actually
  92.             INCREASE the size of the data file slightly, due to the
  93.             overhead needed for sequences between runs.  It also runs
  94.             about 10% slower than the 8 bit version due to the use of
  95.             shifts and logical operators.  Mainly it was an experiment
  96.             that yielded disappointing results.  However, here it is,
  97.             for you to use and abuse.
  98.  
  99.         5)  Portability -- this program is "pretty portable."  The stuff
  100.             dealing with dos filenames should be removed, but that should
  101.             be about it, unless you want to make the datafiles portable
  102.             too, which is another story.
  103.  
  104.         6)  There is a lack of error checking when bytes are written out
  105.             to the output file.  Bytes are written in lots of places,
  106.             and I didn't get around to doing error checking on any of them,
  107.             since my application was going to run only in memory, and
  108.             all the fputc() calls were going to be changed to pokes or
  109.             pointer-directed stuffing.  If you are going to use this program
  110.             in a disk based application, you should really put EOF checks
  111.             after each fputc().
  112.  
  113. Author:  atman%ecst.csuchico.edu@RELAY.CS.NET (internet)
  114.          1@9651                               (WWIVnet)
  115.          atman of 1:119/666.0                 (fidonet)
  116.  
  117.  
  118. Tell me hi if you use this program!
  119.